1. Field of the Invention
The present invention relates to a hardware based high performance pattern matching technology for searching a large amount of patterns at high speed, and more particularly, to a high performance pattern matching method using an optimized pattern arranging method capable of applying a larger amount of search patterns to a limited hardware memory.
The present invention was supported by the IT R&D program of Ministry of Information and Communication (MIC) and Institute for Information Technology Advancement (IITA) [Project No.: 2006-S-042-02, Project Title: Development of Signature Generation and Management Technology against Zero-day Attack].
2. Discussion of the Related Art
Various systems have been developed in order to cope with invasion through a network. However, a high speed network such as Gigabit Ethernet and transmission and reception of a large amount of data based on the high speed network request a change in a conventional low speed security analyzing technique.
In order to properly cope with a high speed and large capacity network and with various invasion attempts, a method of analyzing a large amount of data within a short time is required. That is, researches on a new type of security system considering the above are required. However, most of conventional security systems are based on a packet missing ratio and an invasion detecting ratio and have technological limitations on performance.
In order to solve the problem, hardware based pattern matching methods started to be researched and developed to provide a high speed invasion detecting function, a fire wall function, and a virus detecting function. Most of the systems are performed through a method of examining a rule based specific pattern. Therefore, methods whose performance is not deteriorated by the number of applied patterns and the length of string character columns that each pattern has are required. Therefore, a hash based matching method on a hardware chip memory is widely used. However, it is difficult to apply a large number of patterns due to hash collision.
However, since the number of currently known invasion detecting rules is several thousands and the number of string character columns that each of the rules has is between one byte and 100 bytes, it is difficult to apply a large number of rules without deteriorating performance. In addition, unlike a software based system, since a hardware based system accompanies limitations on a memory, a method of effectively applying a large number of harmful traffic patterns is required.
In addition, although limitations on the memory are recovered using an external memory block, it is difficult to prevent performance from deteriorating. Therefore, a method of effectively and maximally arranging the harmful traffic patterns on a limited memory to apply the same without deteriorating performance is required.